package leetcode_800;

/**
 *@author 周杨
 *MaximumLengthOfRepeatedSubarray_718 判断两个数组里最长的重复数组的长度
 *describe:用动态规划 AC 30%
 *2018年10月11日 下午7:54:44
 */
public class MaximumLengthOfRepeatedSubarray_718 {
	public static void main(String[] args) {
		MaximumLengthOfRepeatedSubarray_718 test=new MaximumLengthOfRepeatedSubarray_718();
		System.out.println(test.findLength(new int[] {1,2,3,2,1},new int[] {3,2,1,4,7}));
	}
	
	public int findLength(int[] A, int[] B) {
        int dp[][]=new int[A.length+1][B.length+1];
        int max=0;
        for(int i=1;i<=A.length;++i) {
        	for(int j=1;j<=B.length;++j) {
        		if(A[i-1]==B[j-1]) {
        			dp[i][j]=dp[i-1][j-1]+1;
        		}
        		else
        			dp[i][j]=0;
        		max=Math.max(dp[i][j], max);
        	}
        }
        return max;
    }
}
